package com.zhn;

import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Stack;

/**
 * 给出由小写字母组成的字符串 S，重复项删除操作会选择两个相邻且相同的字母，并删除它们。
 *
 * 在 S 上反复执行重复项删除操作，直到无法继续删除。
 *
 * 在完成所有重复项删除操作后返回最终的字符串。答案保证唯一。
 */
public class RemoveDuplicates {
    public static void main(String[] args) {
        String s = "aabbbbbcd";
        String s1 = removeDuplicates(s);
        System.out.println(s1);
    }
    static String res = "";
    public static String removeDuplicates(String s) {
        ArrayDeque<Character> deque = new ArrayDeque<>();
        char ch;
        for (int i = 0; i < s.length(); i++) {
            //遇到相同的字符就出栈
            ch = s.charAt(i);
            if (deque.isEmpty() || deque.peek() != ch) {
                deque.push(ch);
            } else {
                deque.pop();
            }
        }
        while (!deque.isEmpty()) {
            //头插，出栈以后就是正常顺序，不然还需要重新反转字符串
            res = deque.pop() + res;
        }

        return res;
    }
}
